在 Day 3 的文章尾聲,我們發現:就算檔名不同,只要內容相同,就會產出一樣的雜湊碼,例如:
empty1.txt
跟 empty2.txt
都是空文字檔,產出的雜湊碼都是 e69de29...
,由此我們可以發現,這雜湊碼並非隨機產生的亂碼,而是經歷一套規則產生。
英文全名為 Secure Hash Algorithm,簡稱 SHA,是由美國國家標準技術研究所(National Institute of Standards and Technology,簡稱 NIST)頒布的標準,這些雜湊函式共有下列五大目標:
要同時達成上述四條件感覺好玄,這演算法到底是有什麼神奇魔力,可以達成以上五大目標?讓我們以 git 最開始使用的 SHA-1 雜湊(SHA 的其中一種版本)流程,來看看這加密雜湊函式到底在變什麼魔法。
以上述空白檔案為例,在進入 SHA-1 演算法本體前,會變成:
<object type> <size><\0><content>
這裡建立的 <object type>
是 blob、<size>
為 0、<content>
為空,因此代換後變成:
blob 0\0
這個 blob 0\0
便是 SHA-1 函數的輸入。
值得留意的是,當中包含的資訊僅有「內容」與「內容長度」,而沒有檔案名稱等元資料,因此,文章最開始範例的 empty1.txt
與 empty2.txt
雖然檔名不同,但因為內容一樣(皆為空檔案)、內容長度也一樣(皆為 0),兩者又都是要建立 blob 物件,因此,送進去 SHA-1 函數的輸入自然也一樣,
在取得 blob 0\0
這輸入後,要先對照 ASCII 表轉換成十進制數字(\0為終止符號,因此 ASCII 碼為 0):
98 108 111 98 32 48 0
接著再將十六進制數字轉為二進制:
1100010 1101100 1101111 1100010 100000 110000 0
每個數字應有八位元,若不足八位元,則補上前導 0:
01100010 01101100 01101111 01100010 00100000 00110000 00000000
然後再把這些數字串起來:
01100010011011000110111101100010001000000011000000000000
接下來的步驟沒辦法在有限篇幅中以實例呈現,讓我們改以圖示說明觀念。
目前我們在圖示左上角的紅色星星處,後續步驟號碼可對照下方文字說明:
SHA-1 演算法流程圖解
H0
H1
H2
H3
H4
五個十六進制的數字,與 6. 產生的 80 個小塊做多輪超級複雜的位元運算,產生新的 H0
H1
H2
H3
H4
。H0
H1
H2
H3
H4
串在一起,就是最終的雜湊碼。這些步驟已經讓人看得頭昏眼花,但其實以上說明還忽略了非常多細節,其中又以第 7. 步最為複雜。若對當中的詳細流程有興趣,可參考 ajalt/python-sha1 這個 GitHub 倉儲,以 Python 程式碼實現 SHA-1 的運算過程。
或者我們可以單純做個實驗觀察,透過 git clone
取得該倉儲後,以終端機指令 printf
提供 blob 0\0
的格式化標準輸出給 sha1.py
當引數,即可得空 blob 物件會產生的雜湊碼 e69de29...
:
在對 SHA-1 流程有基本認識後,我們可以用直觀的方式,大致感受這演算法如何達成上述的五大目標(嚴謹的數學證明屬於密碼學範疇,大幅超越 git 文章所要探討的難度):
H0
H1
H2
H3
H4
的大量複雜運算,但不管怎麼算,這五個數都是 8 位數,等到第 8. 步串在一起,則必為 40 位數。值得留意的是,這五大目標的第 5. 點「均勻分布、避免碰撞」已隨著運算技術進步而被破解,因此 SHA-1 現在已被認為是不安全的雜湊演算法,連 git 都在其官方頁面中提及,要從 SHA-1 轉換到更安全的 SHA-256。
我們花了很多篇幅在講 SHA-1 是怎麼算的,但回到最根本的問題是:為什麼 git 要用雜湊碼當識別碼?難道用簡單一點的編號方式,產生每個 git 物件的識別碼不好嗎?還是有什麼資安考量?
Git 在官方文件中提到使用雜湊碼具有以下兩優點:
有了上述兩點特性,一組雜湊碼就能代表唯一且不可變的項目。
雖然上述 git 文件另有提及使用雜湊碼在資安上的額外好處,但在《Tech Talk: Linus Torvalds on git》這場演講中,git 的發明人 Linus Torvalds 則特別強調:使用雜湊碼不是用來處理資安議題,而是要確保資料的一致性。
這就呼應剛剛在文件裡得出的結論:一組雜湊碼就能代表唯一且不可變的項目,當多人協作或橫跨不同平臺時,我們都可以知道「這組雜湊碼對應的檔案內容就是長這樣」,哪怕數年後再把檔案放到其他地方儲存,只要雜湊碼不變,我們就能確定這份檔案(或者說 git 物件)裡面是連「一個位元都沒有被動過」。
Git 使用密碼學中的 SHA 雜湊碼來當作物件的識別,並不是有特別的資安考量,而是可用來確保檔案的一致性。